package com.sufen.seckill.study.LeetCode;

/**
 * @Author sufen
 * @Date 2021/11/12 21:53
 * @Version 1.0
 * 功能描述：
 */
public class t4_215_数组中第K个最大元素 {
    public int findKthLargest(int[] nums,int k){
        int m=nums.length-k;
        quick_sort(nums,0,nums.length-1,m);
        return nums[m];
    }

    public void quick_sort(int[] nums,int left,int right,int m){
        if(left<right){
            int mid=(left+right)/2;
            int tmp=nums[left];
            int i=left;
            int j=right;

            while(i<j){
                while(nums[j]>tmp&&i<j){
                    j--;
                }
                if(i<j){
                    nums[i++]=nums[j];
                }
                while(nums[i]<tmp&&i<j){
                    i++;
                }
                if(i<j){
                    nums[j--]=nums[i];
                }
            }

            nums[i]=tmp;
            if(i==m){
                return;
            }else if(m<i){
                // System.out.println("aaa");
                quick_sort(nums,left,i-1,m);
            }else{
                // System.out.println("bbb");
                quick_sort(nums,i+1,right,m);
            }


        }
    }
}
